package com.yc.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author samuel chen
 * @date 2021/5/21 2:30 下午
 **/
public class Alibaba {

    public static void main(String[] args) {
        int[] arr1 = new int[]{10, 5, 2, 6};
//        Alibaba al = new Alibaba();
//        al.test1(arr1, 100).forEach(e -> {
//            System.out.println(Arrays.toString(e));
//        });
        int i = test3(arr1, 100);
        System.out.println(i);

    }



    //评测题目1:  实现二叉树相加的函数，即将当前二叉树btree1与参数btree2中的数据元素在对应位置处相加
//	       1                      2                    3
//	     /   \                   / \                  / \
//	    2     3        +        3   4       =        5   7
//	   / \   /  \                  / \              / \ / \
//	  4   5 1    2                5   6            4  5 6  8
 public class BTreeNode{
        public int value;
        public BTreeNode left;
    	public BTreeNode right;
 }

    /**
     * 求两个二叉树相加
     * @param tree1
     * @param tree2
     * @return BTreeNode   null...
     **/
    public BTreeNode addTree(BTreeNode tree1, BTreeNode tree2) {
        if (tree1 == null && tree2 == null) {
            return null;
        }
        if (tree2 == null) {
            return tree1;
        }

        // 定义待返回的结果集
        BTreeNode result = new BTreeNode();
        result.left = tree1.left;
        result.right = tree1.right;

        result.value = tree1.value + tree2.value;
        // 递归添加左右节点 result <==> tree1
        result.left = addTree(result.left, tree2.left);
        result.right = addTree(result.right, tree2.right);

        return result;
    }

    /**
     问题：入参: 数组-任意长度的自然数数组, 目标值 K(自然数)
    结果: 打印出所有的相邻数组组合，所有相邻数的组合的乘积小于等于目标值。
    约束：
    1.数组值和目标值均为自然数。
    2.不能暴力for循环处理。
    示例：
    入参数组 = [10, 5, 2, 6], 目标值为 100。
    100下的组合有 [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. 比如[10,2] 或者 [10,6] 或者 [5,6] 因为不相邻，所以不满足要求。

    请打印出所有的可能组合。
    */
    public List<Integer[]> test1(int[] arr, int target) {

        List<Integer[]> result = new ArrayList<>();
        if (arr == null || arr.length == 0) {
            return result;
        }

        // 乘积结果
        int mulResult = 1;
        // 原始数组下标
        int index = 0;

        for (int i=0; i<arr.length; i++) {

            // 定义临时集合组装数据
            List<Integer> list = new ArrayList<>();
            int arrLength = 0;

            mulResult *= arr[i];
            while (mulResult >= target) {
                mulResult /= arr[index++];
                // 结果数组的长度 动态变化
                arrLength ++ ;
                list.add(arr[i-index+1]);
            }

            Integer[] intArr = new Integer[arrLength];
            int arrIndex = 0;
            for (Integer j : list) {
                intArr[arrIndex++] = j;
            }
            result.add(intArr);
        }
        return result;
    }


    public static int test3(int[] nums, int target) {
        if (target < 1) {
            return 0;
        }
        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= target) {
                prod /= nums[left++];
            }
            ans += right - left + 1;
        }
        return ans;
    }


    public List<Integer[]> test2(int[] arr, int target) {
        List<Integer[]> result = new ArrayList<>();
        if (arr == null || arr.length == 0) {
            return result;
        }
        // 定义初始值
        int n = 0;
        int length = arr.length;
        while (0 < length) {

            if (arr[n] < target) {
                Integer[] r = new Integer[]{arr[n]};
                result.add(r);
            } else {
                n++;
                break;
            }

            for (int i = n+1; i < arr.length; i++) {
                int r2 = arr[n] * arr[i];
                if (r2<100) {
                    Integer[] r = new Integer[]{arr[n], arr[i]};
                    result.add(r);
                } else {
                    break;
                }
                for (int j = i - n + 1; j < arr.length; j++) {
                    r2 = r2*arr[j];

                }

            }


        }
        return null;
    }




}
